﻿#include <stdlib.h>
#include <string.h>
#include <memory.h>

#define LP_CORE

#include "lp_map.h"


static uint32_t
hash_ap(const char * dat, size_t size){
     uint32_t hash = 0xAAAAAAAA;
    for(size_t i = 0; i < size; i++){
        if ((i & 1) == 0)
            hash ^= ((hash << 7) ^ dat[i] * (hash >> 3));
        else
            hash ^= (~((hash << 11) + dat[i] ^ (hash >> 5)));
    }
    return hash;
}

static uint32_t
hash_RS(const char * dat, size_t size){
    int b = 378551; int a = 63689;
    uint32_t hash = 0;
    for(size_t i = 0; i < size; i++){
        hash = hash * a + dat[i];
        a = a * b;
    }
    return hash;
}

static uint32_t
hash_JS(const char * dat, size_t size){
     uint32_t hash = 1315423911;
    for(size_t i = 0; i < size; i++)
        hash ^= ((hash << 5) + dat[i] + (hash >> 2));
    return hash;
}

static uint32_t
hash_PJW(const char * dat, size_t size){
    uint32_t BitsInUnsignedInt = (uint32_t)(4 * 8);
    uint32_t ThreeQuarters     = (uint32_t)((BitsInUnsignedInt  * 3) / 4);
    uint32_t OneEighth         = (uint32_t)(BitsInUnsignedInt / 8);
    uint32_t HighBits          = (uint32_t)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
    uint32_t hash = 0;  uint32_t test = 0;
    for(size_t i = 0; i < size; i++){
        hash = (hash << OneEighth) + dat[i];
        if((test = hash & HighBits)  != 0){
            hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));
        }
    }
    return hash;
}

static uint32_t
hash_ELF(const char * dat, size_t size){
     uint32_t hash = 0;  uint32_t x = 0;
    for(size_t i = 0; i < size; i++){
        hash = (hash << 4) + dat[i];
        if((x = hash & 0xF0000000L) != 0)
            hash ^= (x >> 24);
        hash &= ~x;
    }
    return hash;
}

static uint32_t
hash_BKDR(const char * dat, size_t size){
     uint32_t hash = 0;  uint32_t seed = 131; // 31 131 1313 13131 131313 etc..
    for(uint32_t i = 0; i < size; i++)
        hash = (hash * seed) + dat[i];
    return hash;
}

static uint32_t
hash_SDBM(const char * dat, size_t size){
     uint32_t hash = 0;
    for(size_t i = 0; i < size; i++)
        hash = dat[i] + (hash << 6) + (hash << 16) - hash;
    return hash;
}

static uint32_t
hash_DJB(const char * dat, size_t size){
     uint32_t hash = 5381;
    for(size_t i = 0; i < size; i++)
        hash = ((hash << 5) + hash) + dat[i];
    return hash;
}

static uint32_t
hash_DEK(const char * dat, size_t size){
     uint32_t hash = (uint32_t)size;
    for(size_t i = 0; i < size; i++)
        hash = ((hash << 5) ^ (hash >> 27)) ^ dat[i];
    return hash;
}

static LPMapKeyHash gHashWays[] = {
    hash_ap,       // 0
    hash_RS,       // 1
    hash_JS,       // 2
    hash_PJW,      // 3
    hash_ELF,      // 4
    hash_BKDR,     // 5
    hash_SDBM,     // 6
    hash_DJB,      // 7
    hash_DEK,      // 8
};

static int
defaultCompare(const void * k1,
	size_t sz1, const void * k2, size_t sz2){
    if(k1 == k2){ return 1; }
    if(sz1 != sz2){ return 0; }
    return strncmp(k1, k2, sz1) == 0;
}

LP_API uint32_t
lpHash(const char * k, size_t sz, LPHashType type){
    return gHashWays[type](k, sz);
}

LP_API uint32_t
lpMapHash(const char * k, size_t sz){
    return gHashWays[LPHASH_DEK](k, sz);
}

typedef struct{
    const char * k;
    size_t ksz;
    const void * v;
    uint32_t hash;
    int next;
}Node;

struct LPMap{
    Node * slot;
    uint32_t slotCap;
    uint32_t freeNode;
    uint32_t count;
    uint32_t iter;
    LPMapKeyCompare compare;
    LPMapKeyHash keyHash;
};

static unsigned int
findFreeSlot (LPMap * map){
    while(map->freeNode > 0){
        map->freeNode--;
        if(!map->slot[map->freeNode].k){
            return map->freeNode;
        }
    }
    return -1;
}

#define MAIN_SLOT(map, hash) (hash % map->slotCap)
#define GET_NODE(map, i) (&(map->slot[i]))

static inline void
resetFreeNode (LPMap * map){
    while(map->freeNode > 0){
        map->freeNode --;
        if(!GET_NODE(map, map->freeNode)->k){
            break;
        }
    }
}

static Node *
newNode (LPMap * map, uint32_t hash){
    int pos = MAIN_SLOT(map, hash);
    Node * n = GET_NODE(map, pos);
    if(n->k){
        pos  = findFreeSlot(map);
        if(pos == -1){ return NULL; }
        while(n->next >= 0){
            n = GET_NODE(map, n->next);
        }
        n->next = pos;
        n = GET_NODE(map, pos);
    }
    if(pos == (map->freeNode - 1)){
        resetFreeNode(map);
    }
    return n;
}


static void
reposNode (LPMap * map, Node * n){
    Node * rn = newNode(map, n->hash);
    *rn = *n;
    rn->next = -1;
}

static void
resizeSlot (LPMap * map, uint32_t cap){
    if(map->slotCap == 0 || map->slotCap == cap){
        return;
    }
    if(cap == 0){
        free(map->slot);
        map->slotCap = 0;
        return;
    }
    size_t old_cap = map->slotCap;

    Node * old_slot = map->slot;
    map->slot = malloc(sizeof(Node) * cap);
    memset(map->slot, 0, sizeof(Node) * cap);
    map->slotCap = cap;
    map->freeNode = cap;

    Node * n;
    for(int i = 0; i < old_cap; i ++){
        n = &(old_slot[i]);
        if(n->k){ reposNode(map, n); }
    }
    free(old_slot);
}

static uint32_t
optimizeCap (uint32_t cap){
    for(int i = 1; ; i ++){
        if(((uint32_t)1 << i) >= cap){
            return 1 << i;
        }
    }
    return 0;
}

LP_API LPMap *
lpNewMap(uint32_t cap){
    LPMap * map = malloc(sizeof(LPMap));
    memset(map, 0, sizeof(LPMap));
    cap = optimizeCap(cap);
    map->slot = malloc(sizeof(Node) * cap);
    memset(map->slot, 0, sizeof(Node) * cap);
    map->slotCap = cap;
    map->freeNode = cap;
    map->compare = defaultCompare;
    map->keyHash = lpMapHash;
    return map;
}

LP_API void
lpFreeMap(LPMap * map){
    if(map->slotCap){
        for(uint32_t i = 0; i < map->slotCap; i ++){
            Node * n = &(map->slot[i]);
            if(n->k){
                free((void *)n->k);
            }
        }
        free(map->slot);
    }
    free(map);
}

LP_API void
lpExpandMap(LPMap * map, uint32_t cap){
    cap += map->count;
    if(cap <= map->slotCap){ return; }
    resizeSlot(map, optimizeCap(cap));
}

LP_API void
lpPutMap (LPMap * map,
        const void * k, size_t ksz, const void * v){
    uint32_t hash = map->keyHash((const char *)k, ksz);
    Node * n = GET_NODE(map, MAIN_SLOT(map, hash));
    while (n && n->k) {
        if (n->hash == hash &&
            map->compare(n->k, n->ksz, k, ksz)) {
            break;
        }
        else {
            n = n->next >= 0 ? GET_NODE(map, n->next) : NULL;
        }
    }
    if(n && n->k){ n->v = v; return; }
    n = newNode(map, hash);
    if(!n){
        resizeSlot(map, map->slotCap * 2);
        n = newNode(map, hash);
    }
    n->k = k;
    n->ksz = ksz;
    n->hash = hash;
    n->next = -1;
    n->v = v;
}

LP_API int
lpDelMap (LPMap * map, const void * k, size_t ksz){
    uint32_t hash = map->keyHash((const char *)k, ksz);
    uint32_t pos = MAIN_SLOT(map, hash);
    Node * main = GET_NODE(map, pos);
    if (!main->k) { return 0; }
    Node * n = main;
    Node * pre = main;
    while(n){
        if(n->hash == hash && 
            map->compare(n->k, n->ksz, k, ksz)){
            break;
        }else{
            pos = n->next;
            n = n->next >= 0 ? GET_NODE(map, n->next):NULL;
        }
    }
    if(!n){ return 0; }
    map->count --;
    if(n == main){
        n = n = n->next >= 0 ? GET_NODE(map, n->next):NULL;
        if(n){
            *main = *n;
            n->k = NULL;
        }else{
            main->k = NULL;
        }
    }else{
       n->k = NULL;
       if (pre) { pre->next = n->next; }
       n->next = -1;
    }
    if (pos >= map->freeNode) {
        map->freeNode = pos + 1;
    }
    return 1;
}

LP_API int
lpFindInMap(LPMap * map,
        const void * k, size_t ksz, const void ** v){
    uint32_t hash = map->keyHash((const char*)k, ksz);
    Node * main = GET_NODE(map, MAIN_SLOT(map, hash));
    if (!main->k) { return 0; }
    Node * n = main;
    while(n){
        if(n->hash == hash && 
            map->compare(n->k, n->ksz, k, ksz)){
            break;
        }else{
            n = n->next >= 0 ? GET_NODE(map, n->next):NULL;
        }
    }
    if(n){ *v = n->v; return 1; }
    else{ return 0; }
}

LP_API size_t
lpCountMap (LPMap * map){
    return map->count;
}

LP_API void
lpBeginMap (LPMap * map){
    map->iter = 0;
}

LP_API int
lpNextMap (LPMap * map,
    const void ** k, size_t * ksz, const void ** v){
    Node * n;
    for(;;){
        if(map->iter >= map->slotCap){ return 0; }
        n = GET_NODE(map, map->iter);
        map->iter ++;
        if(n->k){
            *k = n->k;
            *ksz = n->ksz;
            *v = n->v;
            return 1;
        }
    }
    return 0;
}
